package pers.qianyu.month_202102.date_20210206;

import org.junit.*;

/**
 * 698. 划分为k个相等的子集
 * https://leetcode-cn.com/problems/partition-to-k-equal-sum-subsets/
 *
 * @author mizzle rain
 * @date 2021-02-06 9:57
 */
public class CanPartitionKSubsets {
    private int[] nums;
    private int target;
    private boolean[] visited;

    public boolean canPartitionKSubsets(int[] nums, int k) {
        this.nums = nums;
        this.visited = new boolean[nums.length];
        int sum = 0;
        for (int x : nums) sum += x;
        if (sum % k != 0) return false;
        this.target = sum / k;
        return backTracking(0, 0, k);
    }

    private boolean backTracking(int cur, int start, int k) {
        if (k == 0) return true;
        if (cur == target) {
            return backTracking(0, 0, k - 1);
        }
        for (int i = start; i < nums.length; i++) {
            if (!visited[i] && nums[i] + cur <= target) {
                visited[i] = true;
                if (backTracking(cur + nums[i], i + 1, k)) return true;
                visited[i] = false;
            }
        }
        return false;
    }


    @Test
    public void test1() {
        boolean result = new CanPartitionKSubsets()
                .canPartitionKSubsets(new int[]{4, 3, 2, 3, 5, 6, 1}, 4);
        System.out.println("result = " + result);
    }
}
